#define true    1
#define false   0

#define MAX_LEN 100


#define ELEM_NULL 0     // initial value for Elem type


enum Status {OK, ERR};

typedef char bool;
typedef int Elem;       //element type
typedef int Status;     //Status to return
typedef int ListIdx;     //type of index for iterating list
typedef struct LinkList LinkList;   // just for shortcut
typedef struct Node Node;


struct Node {
    struct Node *prev;
    struct Node *next;
    Elem data;
};


/* Description：
 *      结构体LinkList的head和tail成员是一个结构体的变量，而不是指向结构体
 *      的指针。这样结构体LinkList一定至少包含两个Node，应该能减少出错的几
 *      率，而如果使用指针，head或tail可能成为野指针。当然，这可能会带来
 *      使用上的一些疑惑，但是这些会在编译阶段报错，而且只要了解了这个结
 *      构体的思路，应该很快就能适应。相比之下，使用指针编译阶段容易过，
 *      但运行时可能出现莫名其妙的问题。
 *      
 *
 *      另一方面，head是一个实体的Node，则其数据域（即data成员）可以用来储
 *      存链表的初始化信息，从而程序判断链表是否已经初始化。
 *
 *      头结点和尾结点均不存储用户数据。由于链表一开始就包含头节点和尾结点，
 *      所以初始长度应为2，但是考虑到这两个结点均不起存储作用，所以length
 *      的值为实际长度减2，且初始化时设为0。也因此，position为0的结点不是head，
 *      而是head->next。
 */
struct LinkList{
    struct Node head;
    struct Node tail;

    ListIdx length;
    ListIdx max_length;
};


bool check_pos(LinkList *, ListIdx, bool);
bool check_init(LinkList *);
bool check_max_length(LinkList *);


void concat_nodes(Node *, Node *);
Node *_node_addr(LinkList *, ListIdx);


Status initList(LinkList *ls, int max_length);
Status destoryList(LinkList *);
Status insert(LinkList *, ListIdx, Elem);
Status _remove(LinkList *, ListIdx);  // seems to be conflicted with remove() in stdio.h
Status get_elem(LinkList *, ListIdx, Elem *);
Status set_elem(LinkList *, ListIdx, Elem);
bool has_elem(LinkList*, Elem);
